
//34.在排序数组中查找元素的第一个和最后一个位置
class Solution {

    //左闭右闭
    int lower_bound1(vector<int>& nums,int target)
    {
        int n=nums.size();
        int left=0;
        int right=n-1;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target) left=mid+1;  
            else right=mid-1;
        }
        return left;
    }

    //半开半闭
    int lower_bound2(vector<int>& nums,int target)
    {
        int n=nums.size();
        int left=-1;   //left初始化为-1，-1位置是开区间
        int right=n-1;
        while(left<right)
        {
            int mid=left+(right-left+1)/2;   //向上取整防止死循环
            if(nums[mid]<target) left=mid;   //缩小到(mid,right]
            else right=mid-1;                  //缩小到(left,mid-1]
        }
        return left+1;  //或right+1
    }

    //左开右开
    int lower_bound3(vector<int>& nums,int target)
    {
        int n=nums.size();
        int left=-1;   //left初始化为-1，-1位置是开区间
        int right=n;
        while(left+1<right)
        {
            int mid=left+(right-left)/2;  
            if(nums[mid]<target) left=mid;   //缩小到(mid,right)
            else right=mid;                  //缩小到(left,mid-1)
        }
        return right;
    }

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n=nums.size();
        int start=lower_bound1(nums,target);
        if(start==n||nums[start]!=target) return {-1,-1};  //不存在target的值，直接返回

        int end=lower_bound1(nums,target+1)-1;  //查找最后一个target
        return {start,end};
    }
};